Computer programs which provide spreadsheet functions are extremely popular in today's computer-assisted workplace. The row and column structure of spreadsheet programs provides users an easily understood means for comparing and contrasting numbers and other data.
In order to expand the flexibility and scope of spreadsheet and other analytical programs, and to facilitate multiple-user access, it is known to organize the data for such programs in the format of a multidimensional array, e.g., the orthogonal coordinates or dimensions of perceptible space. For more complicated applications, however, more than three coordinates or dimensions are required. Such an organizational structure is disclosed in my U.S. Pat. No. 5,319,777, the subject matter of which is incorporated herein by reference.
The organizational structure of a multidimensional array is illustrated in FIG. 1. Each value within this structure is uniquely identified by a set of elements. One element is provided for each dimension of the array. The multidimensional array illustrated in FIG. 1 has four dimensions, labeled a, b, c and d in this figure.
For the purpose of this illustration, the values stored within the multidimensional array can be viewed as monetary values representing the monthly budget for the departments of a corporation over several years. The a, b, c, and d dimensions represent, respectively, expense items, months, departments, and years. Each monetary value within the array is assigned a cellular location which is uniquely identified by one element for each dimension. If this same structure were applied to each of a number of subsidiaries of the corporation, five dimensions would be required.
In order to store within a computer's database values organized in the form of a multidimensional array, each potential storage location within the array can be assigned and uniquely identified upon establishing the array. For example, in a three-dimensional array with ten elements for each dimension, one thousand potential storage locations for potential values exist. Upon establishing the multidimensional array within the computer's database, each of these one thousand potential storage locations, or potential storage cells, can be allocated within the database and uniquely identified in relation to the ten elements for each dimension. To insert into, or withdraw from, the multidimensional array a particular value, therefore, the value's location is calculated from the value's element identifiers and the insertion or withdrawal step then effected. The advantage of this scheme is speed and simplicity.
The principal disadvantage of this scheme is that the number of potential values within a typical multidimensional array can be extremely large. The number of values actually stored, however, often is relatively small. Allocating storage locations for each of the potential values within a typical multidimensional array, therefore, can exceed the storage capacity of a personal computer or file server before any values are stored.
In order to overcome this problem, a storage and retrieval scheme has been implemented for values within a multidimensional array using a hierarchy of database-pointers. This scheme is illustrated in FIG. 2.
In accordance with this scheme, the number of dimensions comprising the array, and the number of elements comprising each dimension of the array, are determined before establishing the array. Many of the array's potential storage locations are not assigned within the computer's memory or database, however, until values actually are stored within the array.
To store a value, the elements corresponding to the value are determined. Assume, e.g., that the elements for a value v.sub.1 are a.sub.1, b.sub.2, c.sub.3 and x.sub.2 for the first, second, third and last dimension, respectively. A storage node 1 corresponding to the array's first dimension, as shown in FIG. 2, then is established within the computer's database, and space within this storage node is allocated for all of the elements corresponding to this dimension (a.sub.1, a.sub.2, a.sub.3, . . . , a.sub.n). A database-pointer 3 then is stored in a storage location a.sub.1 within this storage node corresponding to the element for the value's first dimension.
A second storage node 5 then is established within the computer's database corresponding to database-pointer 3 and to the array's second dimension. Space within this storage node is allocated for all of the elements corresponding to the second dimension (b.sub.1, b.sub.2, b.sub.3, . . . , b.sub.n). Database-pointer 3 is caused to point to storage node 5. A database-pointer 7 is stored within storage node 5 at a storage location b.sub.2 corresponding to the element for the value's second dimension.
A third storage node 9 then is established within the computer's database corresponding to database-pointer 7 and also to the array's third dimension. Space within this third storage node is allocated for all of the elements within the array's third dimension (c.sub.1, c.sub.2, c.sub.3, . . . , c.sub.n). Database-pointer 7 is caused to point to storage node 9. A database-pointer 11 is stored within storage node 9 at a storage location c.sub.3 corresponding to the element for the value's third dimension.
These steps are repeated for each of the array's dimensions until a storage node 13, corresponding to the array's last dimension, is established. The value v.sub.1 is stored in a storage location x.sub.2 corresponding to the element for the value's last dimension.
When a second value is stored within the multidimensional array, similar steps are effected. If the element corresponding to the second value's first dimension is the same as that for the first value, no new database pointer is stored in storage node 1. On the other hand, if the element corresponding to the second value's first dimension is different from that for the first value, e.g., is a.sub.3, then a second database-pointer 15 is stored within storage node 1 at a storage location a.sub.3 corresponding to this element.
A new storage node 17 then is established within the computer's database, in a manner similar to that described above, corresponding to database-pointer 15 and also to the array's second dimension. Space within storage node 17 is allocated for all of the elements of the second dimension (b.sub.1, b.sub.2, b.sub.3, . . . , b.sub.n). Database-pointer 15 is caused to point to storage node 17. A database-pointer 19 is stored within storage node 17 at a storage location b.sub.2 corresponding to the element for the second value's second dimension. These steps are repeated, as for the first value, until the second value v.sub.2 is stored in a storage node 21 at a storage location x.sub.3, corresponding, respectively, to the array's last dimension and the second value's element for this dimension.
If the element corresponding to the first dimension are the same for the first value and the second value, a database-pointer 23 corresponding to the element for the second value's second dimension is stored in storage node 5. This storage node is the same storage node in which database-pointer 7 is stored which corresponds to the element for the first value's second dimension. Assuming the elements for the first and second values' second dimension are different, the hierarchical tree of database-pointers for these values splits at storage node 5, rather than storage node 1.
In accordance with this scheme, therefore, in order to insert into, or withdraw from, the multidimensional array a particular value, the element identifiers corresponding to the value are determined. For the insertion step, database-pointers, and finally the value, are placed within storage nodes corresponding to the array's various dimensions. The value is withdrawn from memory by tracing the hierarchy of database-pointers defined by the value's element identifiers.
Under this scheme, notwithstanding that the size of a multidimensional array is defined (viz., the number of dimensions and the number of elements within each dimension), the allocation of space within a computer's memory upon establishing the array, for all of the array's potential values and all of the array's corresponding potential storage locations, is avoided. The amount of memory allocated is proportional to the number of values actually stored. This scheme avoids allocating huge blocks of a computer's memory to unused storage cells.
For large, sparsely populated multidimensional arrays, however, this scheme nevertheless results in substantial inefficiencies. For example, as shown in FIG. 1, only one database-pointer 11 is stored in storage node 9 at storage location c.sub.3. Nevertheless, space is allocated within the computer's memory for storage cells corresponding to all of the elements within the array's third dimension, viz., c.sub.1, c.sub.2, c.sub.3, . . . , c.sub.n. If a subsequently stored value is defined by elements a.sub.1 and b.sub.2 for the first and second dimensions, respectively, then a second database-pointer will be stored within storage node 9. For sparsely populated arrays, however, the probability is substantial that such a second value will not exist. This probability increases, moreover, for storage nodes corresponding to the array's higher dimensions. As a result, for such multidimensional arrays, large amounts of the computer's memory are wasted.
The values stored within a multidimensional array can include values which are dependent upon other values. For example, as discussed in my U.S. Pat. No. 5,319,777, a multidimensional array may include "consolidation values," i.e. values which are, dependent upon a group of values within the multidimensional array whose element identifiers differ only with respect to one dimension of the array.
For example, as discussed above, the a, b, c and d dimensions of the array illustrated in FIG. 1 represent, respectively, expense items, months, departments and years. If this array also were to include quarterly and yearly averages for each expense item for a particular department in a given year, such averages would represent consolidation values. Each such value is calculated from other values within the array whose elements differ only with respect to one dimension, viz., the monthly dimension.
Consolidation values may be stored within a multidimensional array in the same manner as any other values. The only requirement is the addition of elements to the dimensions of the array for which consolidation values are provided. These additional elements define storage locations within the array in which these consolidation values are stored. In the alternative, database-pointers to the formulas used to calculate these consolidation values may be stored in these locations.
Consolidation values are calculated from simple formulas, viz., weighted sums of other values in a dimension. Also, the identity of the formula applicable to a particular consolidation value, even for large multidimensional arrays, depends upon only one element of one dimension. For example, in the multidimensional array discussed above, element b.sub.n+1 can specify the formula for calculating quarterly averages, and element b.sub.n+2 can specify the formula for calculating yearly averages.
In order to determine the applicability of a particular consolidation formula, the elements corresponding to a requested value are examined for the elements of each dimension corresponding to consolidation values. If such an element is present, the program diverts to the applicable consolidation formula. The program associated with this formula, based upon the other elements corresponding to the requested value, then withdraws the necessary values from the multidimensional array, performs the consolidation, and displays the result to the user. This scheme, therefore, avoids storing the consolidation values, and database-pointers to formulas for calculating the consolidation values, within the multidimensional array.
This scheme, however, cannot be applied to general formulas whose applicability depend upon a plurality of elements distributed randomly throughout the array's various dimensions. The values calculated from such formulas, moreover, can be dependent upon any value stored randomly throughout the multidimensional array.
To provide such calculated values, database-pointers to the applicable formulas are stored within all of the applicable storage locations or storage cells corresponding to the calculated values. For large, sparsely populated multidimensional arrays, this scheme results in the allocation of large blocks of the computer's memory for storing database-pointers pointing to the same formulas.